{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过前面的学习，已经接触到了线性表和树两种数据结构。对于之间具有“一对一”关系的数据，可以选择使用线性表进行表示和存储；之间具有“一对多”关系的数据，可以考虑使用树进行表示和存储。除此之外，对于之间还可能具有“多对多”关系的数据，数据结构表示和存储这类数据的结构使用的是——图。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 基本概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 顶点:  \n",
    "    使用图表示的每个数据元素称作顶点（Vertex），图中所有顶点构成的集合习惯上用 V 表示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 有(无)向图 ： \n",
    "    之间只具有单向关系的顶点构成的图称为有向图，如图1（A）；之间具有双向关系的顶点构成的图称为无向图，如图1（B）\n",
    "\n",
    "<img src=\"image/chapter06/Figure1.png\" width=500>\n",
    "$$ 图1 有向图和无向图 $$\n",
    "\n",
    "图1（A） 表示的就是一个有向图，其中 V1、V2、V3、V4 都是构成图的顶点，用集合 V 表示为：{V1,V2,V3,V4}。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### “弧”和“边”\n",
    "    在有向图中，<v,w> 表示为从 v 到 w 的一条弧；在无向图中，（v,w）表示为顶点 v 和顶点 w 之间的一条边"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 完全图\n",
    "    对于无向图来说，如果图中每个顶点都和除自身之外的所有顶点有关系，那么就称这样的无向图为完全图。如图2所示就是一个完全图。\n",
    "    \n",
    "<img src=\"image/chapter06/Figure2.png\" width=250>\n",
    "$$ 图２ 完全图 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 有向完全图\n",
    "对于有向图来说，通过图中的每个顶点，都能找到图中的所有其它的顶点，那么就称这样的有向图为有向完全图。如图 3 所示就是一个有向完全图。\n",
    "\n",
    "<img src=\"image/chapter06/Figure3.png\" width=250>\n",
    "$$ 图3 有向完全图 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 出度和入度\n",
    "在有向图中，对于一个顶点 v 来说，箭头指向顶点 v 的弧的数目为该顶点的入度；箭头远离顶点 v 的弧的数目为该顶点的出度。有向图顶点的度就是该顶点出度和入度的和。例如图 1（A）中，顶点 V1 的入度为 1 ，出度为 2 ，所以顶点V1的度为 3 。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 入路径和回路\n",
    "路径 ：在图中从一个顶点到另一个顶点所走过的多个顶点组成的序列，就称为“路径”。 在有向图中，路径是有向的。如果在路径中第一个顶点和最后一个顶点相同，此路径称为“回路”或“环”。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 连通图\n",
    "在无向图中，如果一个顶点到另一个顶点存在至少一条路径，称它们之间是连通的。 如果图中任意两个顶点之间都是连通的，则此图为连通图。例如图 1（B）就是一个连通图。 如果一个图本身不是连通图，但是图中某个子图是连通图，那么这个子图又被称为“连通分量”。\n",
    "\n",
    "<img src=\"image/chapter06/Figure4.png\" width=800>\n",
    "$$ 图4 连通分量 $$\n",
    "\n",
    "例如，图 4（a）中本身不是连通图，但是本身有 3 个连通分量，如（B）所示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 强连通图\n",
    "在有向图中，如果任意一对顶点 Vi 和 Vj，从 Vi 到 Vj 和从 Vj 到 Vi 都含有至少一条通路，那么称此图为强连通图。如果有向图的连通分量也具有此特征，则为强连通分量。\n",
    "\n",
    "<img src=\"image/chapter06/Figure5.png\" width=200>\n",
    "$$ 图5 强连通图 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 生成树和森林\n",
    "\n",
    "对于连通图来说，如果对其进行遍历，遍历过程中经过的顶点和边其实质是一棵树，在这里称之为“生成树”。由于连通图中，任意两顶点之间可能含有多条通路，所以一个连通图可能会对应多个生成树。\n",
    "\n",
    "<img src=\"image/chapter06/Figure6.png\" width=500>\n",
    "$$ 图6 连通图及其生成树 $$\n",
    "\n",
    "例如，图 6（A）是一个连通图，（B）为它的生成树（不唯一）。连通图的生成树中，边的数量永远要比顶点的数量少1。如果少更多，顶点之间无法做到连通；反之，生成树中会存在回路（环）。 \n",
    "\n",
    "生成树是针对于连通图而言的，如果是非连通图，其中含有的多个连通分量，每个连通分量对应不止一棵生成树，所以非连通图对应的是由多棵生成树组成的生成森林。\n",
    "\n",
    "<img src=\"image/chapter06/Figure7.png\" width=500>\n",
    "\n",
    "$$ 图7 非连通图的生成森林 $$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 存储方式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "图，包括无向图和有向图；网，是指带权的图，包括无向网和有向网。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 图\n",
    "在图中，如果各顶点没有权值，所以如果两顶点之间有关联，相应位置记为 1 ；反之记为 0 .对于无向图来说，二维数组构建的二阶矩阵，实际上是对称矩阵.而在有向图中，由于关联具有方向性，因此这个二阶矩阵不一定是对称的。\n",
    "\n",
    "<img src=\"image/chapter06/Figure8.png\" width=500>\n",
    "\n",
    "$$ 图8 有向图和无向图 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "无向图的二维矩阵\n",
    "<img src=\"image/chapter06/Figure9.png\" width=200>\n",
    "有向图的二维矩阵\n",
    "<img src=\"image/chapter06/Figure10.png\" width=200>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 网"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构建无向网和有向网时，对于之间没有边或弧的顶点，相应的二阶矩阵中存放的是 0。目的只是为了方便查看运行结果，而实际上如果顶点之间没有关联，它们之间的距离应该是无穷大（∞）。\n",
    "\n",
    "<img src=\"image/chapter06/Figure11.png\" width=600>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
